package com.cwj;

import java.util.List;
import java.util.Map;
import java.util.TreeMap;

public class MathUtil {


    /**
     * 求组合数
     * m 中取 n个数字
     * 然而对于C_{m}^{n} =C_{m}^{n - 1} + C_{m - 1} ^{n - 1} 有这样的关系
     */
    public static long comb(long m, long n) {
        if (n == 1) return m;
        if (n == m || n == 0) return 1;
        return comb(m - 1, n - 1) + comb(m - 1, n);
    }

    /**
     * 最大公约数
     */
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    public static int gcd2(int a, int b) {
        int r;
        while (b != 0) {
            r = a % b;
            a = b;
            b = r; // 辗转相除
        }
        return a;
    }

    /**
     * 最小公倍数
     */
    public static int lcm(int a, int b) {
        return (a / gcd(a, b) * b);
    }

    /**
     * 在nums中找大于等于target的第一个数字
     */
    public static int ceilingIndex(int[] nums, int target) {
        if (target > nums[nums.length - 1]) return -1;
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public static int higherIdx(int[] nums, int target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }

    public static int ceilingIndex2(int[] nums, int target) {
        TreeMap<Integer, Integer> map = new TreeMap<>(Map.of(Integer.MAX_VALUE, nums.length));
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        return map.ceilingEntry(target).getValue();
    }

    /**
     * 在nums中找小于等于target的第一个数
     */
    public static int floorIndex(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int ans = -1;
        while (l <= r) {
            int mid = (r - l) >> 1 + l;
            if (nums[mid] > target) {
                r = mid - 1;
            } else {
                ans = mid;
                l = mid + 1;
            }
        }
        return ans;
    }

    public static int lowerIndex(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        int ans = -1;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (nums[mid] >= target) {
                r = mid - 1;
            } else {
                ans = mid;
                l = mid + 1;
            }
        }
        return ans;
    }

    public static int lowerIndex(List<Integer> list, int target) {
        if (list.isEmpty() || target <= list.get(0)) return -1;
        int l = 0, r = list.size() - 1;
        int ans = 0;
        while (l <= r) {
            int mid = (r - l) / 2 + l;
            if (list.get(mid) >= target) {
                r = mid - 1;
            } else {
                ans = mid;
                l = mid + 1;
            }
        }
        return ans;
    }

    /**
     * 素数
     */
    public boolean isPrime(int N) {
        if (N < 2) return false;
        int R = (int) Math.sqrt(N);
        for (int d = 2; d <= R; ++d)
            if (N % d == 0) return false;
        return true;
    }

    /**
     * 快速幂算法
     */
    public long quickMul(int x, int y) {
        if (y == 0) return 1;
        long res = quickMul(x, y >> 1);
        return (y & 1) == 1 ? res * res * x : res * res;
    }

    /**
     * 二分查看target
     *
     * @param nums
     * @param target
     * @return
     */
    public int binarySearch(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }


}
